// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

#![allow(dead_code)]

use std::cmp::Ordering;
use std::fmt::Debug;

/// A node in the singly linked list.
#[derive(Debug)]
pub struct SListEntry<T> {
    data: T,
    next: Option<Box<SListEntry<T>>>,
}

/// A singly linked list.
#[derive(Debug)]
pub struct SList<T> {
    head: Option<Box<SListEntry<T>>>,
    length: usize,
}

impl<T> SList<T> {
    /// Creates a new empty list.
    pub fn new() -> Self {
        SList { head: None, length: 0 }
    }

    /// Appends an element to the end of the list.
    pub fn append(&mut self, data: T) {
        let new_node = Box::new(SListEntry { data, next: None });
        if let Some(mut current) = self.head.take() {
            while let Some(ref mut next) = current.next {
                current = next.take();
            }
            current.next = Some(new_node);
        } else {
            self.head = Some(new_node);
        }
        self.length += 1;
    }

    /// Prepends an element to the beginning of the list.
    pub fn prepend(&mut self, data: T) {
        let new_node = Box::new(SListEntry {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_node);
        self.length += 1;
    }

    /// Returns the length of the list.
    pub fn length(&self) -> usize {
        self.length
    }

    /// Returns the data at the nth position in the list.
    pub fn nth_data(&self, index: usize) -> Option<&T> {
        let mut current = &self.head;
        for _ in 0..index {
            if let Some(ref node) = current {
                current = &node.next;
            } else {
                return None;
            }
        }
        current.as_ref().map(|node| &node.data)
    }

    /// Removes the entry at the given index.
    pub fn remove_entry(&mut self, index: usize) -> Option<T> {
        if index >= self.length {
            return None;
        }
        let mut current = &mut self.head;
        for _ in 0..index {
            if let Some(ref mut node) = current {
                current = &mut node.next;
            }
        }
        let removed = current.take().map(|node| {
            *current = node.next;
            node.data
        });
        if removed.is_some() {
            self.length -= 1;
        }
        removed
    }

    /// Sorts the list using the given comparator function.
    pub fn sort<F>(&mut self, compare: F)
    where
        F: Fn(&T, &T) -> Ordering,
    {
        let mut vec = Vec::new();
        while let Some(mut node) = self.head.take() {
            self.head = node.next.take();
            vec.push(node.data);
        }
        vec.sort_by(compare);
        for data in vec.into_iter().rev() {
            self.prepend(data);
        }
    }

    /// Finds the first entry that matches the given predicate.
    pub fn find_data<F>(&self, predicate: F) -> Option<&T>
    where
        F: Fn(&T) -> bool,
    {
        let mut current = &self.head;
        while let Some(ref node) = current {
            if predicate(&node.data) {
                return Some(&node.data);
            }
            current = &node.next;
        }
        None
    }

    /// Converts the list to an array.
    pub fn to_array(&self) -> Vec<&T> {
        let mut array = Vec::new();
        let mut current = &self.head;
        while let Some(ref node) = current {
            array.push(&node.data);
            current = &node.next;
        }
        array
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_slist_append() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        assert_eq!(list.length(), 4);
        assert_eq!(list.nth_data(0), Some(&variable1));
        assert_eq!(list.nth_data(1), Some(&variable2));
        assert_eq!(list.nth_data(2), Some(&variable3));
        assert_eq!(list.nth_data(3), Some(&variable4));
    }

    #[test]
    fn test_slist_prepend() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.prepend(variable1);
        list.prepend(variable2);
        list.prepend(variable3);
        list.prepend(variable4);

        assert_eq!(list.length(), 4);
        assert_eq!(list.nth_data(0), Some(&variable4));
        assert_eq!(list.nth_data(1), Some(&variable3));
        assert_eq!(list.nth_data(2), Some(&variable2));
        assert_eq!(list.nth_data(3), Some(&variable1));
    }

    #[test]
    fn test_slist_free() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        // In Rust, we don't need to manually free the list.
        // The list will be dropped automatically when it goes out of scope.
    }

    #[test]
    fn test_slist_next() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        let mut current = &list.head;
        assert_eq!(current.as_ref().map(|node| &node.data), Some(&variable1));
        current = &current.as_ref().unwrap().next;
        assert_eq!(current.as_ref().map(|node| &node.data), Some(&variable2));
        current = &current.as_ref().unwrap().next;
        assert_eq!(current.as_ref().map(|node| &node.data), Some(&variable3));
        current = &current.as_ref().unwrap().next;
        assert_eq!(current.as_ref().map(|node| &node.data), Some(&variable4));
        current = &current.as_ref().unwrap().next;
        assert_eq!(current, &None);
    }

    #[test]
    fn test_slist_nth_entry() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        assert_eq!(list.nth_data(0), Some(&variable1));
        assert_eq!(list.nth_data(1), Some(&variable2));
        assert_eq!(list.nth_data(2), Some(&variable3));
        assert_eq!(list.nth_data(3), Some(&variable4));
        assert_eq!(list.nth_data(4), None);
        assert_eq!(list.nth_data(400), None);
    }

    #[test]
    fn test_slist_length() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        assert_eq!(list.length(), 4);

        list.prepend(variable1);
        assert_eq!(list.length(), 5);
    }

    #[test]
    fn test_slist_remove_entry() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        assert_eq!(list.remove_entry(2), Some(variable3));
        assert_eq!(list.length(), 3);

        assert_eq!(list.remove_entry(0), Some(variable1));
        assert_eq!(list.length(), 2);

        assert_eq!(list.remove_entry(0), Some(variable2));
        assert_eq!(list.remove_entry(0), Some(variable4));
        assert_eq!(list.remove_entry(0), None);
    }

    #[test]
    fn test_slist_sort() {
        let mut list = SList::new();
        let entries = [89, 4, 23, 42, 4, 16, 15, 4, 8, 99, 50, 30, 4];
        let sorted = [4, 4, 4, 4, 8, 15, 16, 23, 30, 42, 50, 89, 99];

        for &entry in entries.iter() {
            list.prepend(entry);
        }

        list.sort(|a, b| a.cmp(b));

        assert_eq!(list.length(), sorted.len());

        for (i, &value) in sorted.iter().enumerate() {
            assert_eq!(list.nth_data(i), Some(&value));
        }
    }

    #[test]
    fn test_slist_find_data() {
        let mut list = SList::new();
        let entries = [89, 23, 42, 16, 15, 4, 8, 99, 50, 30];

        for &entry in entries.iter() {
            list.append(entry);
        }

        for &entry in entries.iter() {
            assert_eq!(list.find_data(|&x| x == entry), Some(&entry));
        }

        assert_eq!(list.find_data(|&x| x == 0), None);
        assert_eq!(list.find_data(|&x| x == 56), None);
    }

    #[test]
    fn test_slist_to_array() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        let array = list.to_array();
        assert_eq!(array, vec![&variable1, &variable2, &variable3, &variable4]);
    }
}
